package problem131_Palindrome_Partitioning;

import java.util.LinkedList;
import java.util.List;

public class MySolution {
	public List<List<String>> partition(String s) {
		char[] input=s.toCharArray();
		List<List<String>> result=new LinkedList<>();
		dfs(result,new LinkedList<>(), input, 0, input.length-1);
		return result;
    }
	
	private void dfs(List<List<String>> result,List<String> current,char[] s,int start,int end){
		if(start>end){
			result.add(new LinkedList<>(current));
			return;
		}
		for(int i=start;i<=end;i++){
			if(isPalindrome(s,start,i)){
				current.add(charArrayToString(s,start,i));
				dfs(result,current,s,i+1,end);
				current.remove(current.size()-1);
			}
		}
	}
	
	private boolean isPalindrome(char[] s,int start,int end){
		while(start<=end){
			if(s[start]!=s[end]){
				return false;
			}
			start++;
			end--;
		}
		return true;
	}
	
	private String charArrayToString(char[] s,int start,int end){
		StringBuilder sb=new StringBuilder();
		for(int i=start;i<=end;i++){
			sb.append(s[i]);
		}
		return sb.toString();
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().partition("aaba"));
	}
}
